
public class PopularList<S,T>{
	private S key;
	private T value;
	private PopularList<S,T> prev;
	private PopularList<S,T> next;
	private PopularList<S,T> first;
	
	public PopularList(S key,T value){
		this.key=key;
		this.value=value;
		this.prev=null;
		this.next=null;
		first=this;
	}
	
	private PopularList(S key,T value,PopularList<S,T> prev,PopularList<S,T> next,PopularList<S,T> first){
		this.key=key;
		this.value=value;
		this.prev=prev;
		this.next=next;
		this.first=first;
	}

	public boolean add(S key,T value) {
		PopularList<S,T> current=first;
		while(!current.isEmpty()){
			if(current.key.equals(key)){
				return false;
			}
			current=current.next;
		}
		current.next=new PopularList(key,value,current,null,first);
		return true;
	}

	public T contains(S key) {
		PopularList<S,T> current=first;
		boolean found=false;
		while(!current.isEmpty()&&!found){
			if(current.key.equals(key)){
				found=true;
			}
			else{
				current=current.next;
			}
		}
		if(!found){
			return null;
		}
		if(current.prev==null){
			return current.value;
		}
		if(!current.isEmpty()){
			current.next.prev=current.prev;
		}
		current.prev.next=current.next;
		current.next=first;
		first.prev=current;
		first=current;
		current.prev=null;
		current=this;
		while(!current.isEmpty()){
			current.first=first;
			current=current.next;
		}
		return first.value;
	}
	
	public boolean isEmpty(){
		return next==null;
	}
	
	
}
